using System;
using System.Collections.Generic;
using System.Text;
using MathNet.Numerics.LinearAlgebra;
using System.Globalization;

namespace igather.Framework
{
    /// <summary>
    /// An implementation of a graph using a list of adjacencies
    /// </summary>
    public class UndirectedAdjacencyGraph : IGraph
    {		
        private List<Vertex> mVertices;

        private Dictionary<Vertex, List<Edge>> mEdges;

		/// <summary>
		/// Default Constructor 
		/// </summary>
        public UndirectedAdjacencyGraph()
        {
            mVertices = new List<Vertex>();
            mEdges = new Dictionary<Vertex, List<Edge>>();
        }

        #region IGraph Members 

        /// <summary>
        /// Adds a vertex to this graph
        /// </summary>
        /// <param name="v">Vertex to add</param>
        public void AddVertex(Vertex v)
        {
            if (mVertices.IndexOf(v) >= 0)
                throw new ArgumentException("Cannot add duplicate vertex");

            mVertices.Add(v);
            mEdges.Add(v, new List<Edge>());
        }

        /// <summary>
        /// Finds a vertex in the graph
        /// </summary>
        /// <param name="v">Vertex to find</param>
        /// <returns>The vertex if it is found, otherwise false</returns>
        public Vertex GetVertex(Vertex v)
        {
            Vertex result = null;
            int index = mVertices.IndexOf(v);
            if (index >= 0)
                result = mVertices[index];

            return result;
        }

        /// <summary>
        /// Removes a vertex from the graph
        /// </summary>
        /// <param name="v">Vertex to remove</param>
        /// <returns>True if vertex was removed, otherwise false</returns>
        public bool RemoveVertex(Vertex v)
        {
			bool removed = mVertices.Remove(v) && mEdges.Remove(v);
			foreach (List<Edge> adjacencies in mEdges.Values)
				adjacencies.RemoveAll((Edge e) => (e.Tail == v));
            return removed;
        }

        /// <summary>
        /// Gets the list of edges for a vertex
        /// </summary>
        /// <param name="v">Vertex to get the edges from</param>
        /// <returns>The list of edges for a vertex</returns>
        public List<Edge> GetEdges(Vertex v)
        {
            return mEdges[v];
        }

        /// <summary>
        /// Gets the list of vertices in this graph
        /// </summary>
        public List<Vertex> Vertices
        {
            get { return new List<Vertex>(mVertices); }
        }

        /// <summary>
        /// True if this graph is directed, otherwise false
        /// </summary>
        public bool IsDirected
        {
            get { return false; }
        }

        /// <summary>
        /// Creates a new edge from this graph
        /// </summary>
        /// <param name="head">Head vertex for this edge</param>
        /// <param name="tail">Tail vertex for this edge</param>
        /// <param name="weight">Weight of the edge</param>
        /// <returns>An instance of the Edge class</returns>
        public Edge CreateEdge(Vertex head, Vertex tail, double weight)
        {
            return new Edge(IsDirected, head, tail, weight);
        }

        /// <summary>
        /// Creates a new edge from this graph
        /// </summary>
        /// <param name="head">Head vertex for this edge</param>
        /// <param name="tail">Tail vertex for this edge</param>
        /// <returns>An instance of the Edge class</returns>
        public Edge CreateEdge(Vertex head, Vertex tail)
        {
            return CreateEdge(head, tail, 0);
        }

        /// <summary>
        /// Adds an edge to this graph
        /// </summary>
        /// <param name="e">Edge to add</param>
        public void AddEdge(Edge e)
        {
            Edge reversedEdge = new Edge(IsDirected, e.Tail, e.Head, e.Weight);
            if ((mEdges[e.Head].Contains(e)) || (mEdges[e.Tail].Contains(reversedEdge)))
                throw new ArgumentException("Cannot add duplicate edge");

            mEdges[e.Head].Add(e);
            mEdges[e.Tail].Add(reversedEdge);
        }

        /// <summary>
        /// Finds an edge in this graph
        /// </summary>
        /// <param name="e">Edge to find</param>
        /// <returns>The edge if it is found, otherwise null</returns>
        public Edge GetEdge(Edge e)
        {
            Edge result = null;
            foreach (List<Edge> adjacencies in mEdges.Values)
			{
                result = adjacencies.Find((Edge edge) => (edge.Equals(e)));
                if (result != null) break;
			}

            return result;
        }

        /// <summary>
        /// Removes an edge from the graph
        /// </summary>
        /// <param name="e">Edge to remove</param>
        /// <returns>True if edge was removed, otherwise false</returns>
        public bool RemoveEdge(Edge e)
        {
            Edge reversedEdge = new Edge(IsDirected, e.Tail, e.Head, e.Weight);
            return mEdges[e.Head].Remove(e) && mEdges[e.Tail].Remove(reversedEdge);
        }

        /// <summary>
        /// Gets the list of edges with at least one node in this graph
        /// </summary>
        public List<Edge> Edges
        {
            get 
            {
                List<Edge> edges = new List<Edge>();
                foreach (List<Edge> adjacencies in mEdges.Values)
                    edges.AddRange(adjacencies);
                return edges;
            }
        }

		/// <summary>
		/// Create a matrix that represents this graph 
		/// </summary>
		/// <returns>
		/// A matrix representation of this graph
		/// </returns>
		public Matrix ToMatrix()
		{
			int size = Vertices.Count;
			Matrix m = new Matrix(size, size);
			for (int i = 0; i < size; i++)
			{
				List<Edge> edges = GetEdges(Vertices[i]);
				foreach (Edge e in edges)
				{
					if (Vertices.Contains(e.Tail))
						m[i, Vertices.IndexOf(e.Tail)] = e.Weight;
				}
			}

			return m;
		}
		
		/// <summary>
		/// Creates a string representation of this graph 
		/// </summary>
		/// <remarks>
		/// The format used here is GraphViz's
		/// http://www.graphviz.org/
		/// </remarks>
		/// <returns>
		/// A string repreentation of this graph
		/// </returns>
		public override string ToString()
		{
            //Edge edge;
            StringBuilder returnString = new StringBuilder();
            returnString.AppendLine("graph G {");

			foreach (Edge e in Edges)
				if (e.Weight != 0)
					returnString.AppendLine(string.Format("\"{0}\" -- \"{1}\" [label={2}]", e.Head.Name, e.Tail.Name, e.Weight));
			
            returnString.AppendLine("}");
            return returnString.ToString();
		}
		
        #endregion
    }
}
